import java.util.*;

public class demo1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // T: 测试用例的数量
        int T = scanner.nextInt();

        // 遍历每个测试用例
        for (int t = 0; t < T; t++) {
            // n: 小队的数量
            int n = scanner.nextInt();
            // k: 国王希望组成的纯职业小组的数量
            long k = scanner.nextLong();
            // h: HashMap 用于存储每个职业的士兵总数
            // Key: 职业 (a_i)
            // Value: 该职业的士兵总数 (b_i)
            Map<Integer, Long> h = new HashMap<>();
            // 读取每个小队的职业和士兵数量，并更新 HashMap
            for (int i = 0; i < n; i++) {
                int a = scanner.nextInt(); // 第 i 个小队的职业
                long b = scanner.nextLong(); // 第 i 个小队的士兵数量

                // 将该职业的士兵数量添加到 HashMap 中，如果该职业已经存在，则累加数量
                h.put(a, h.getOrDefault(a, 0L) + b);
            }
            // b: ArrayList 用于存储每个职业的士兵总数 (从 HashMap 中提取)
            List<Long> b = new ArrayList<>(h.values());
            // cnt: 可以组成的完整纯职业小组 (3人一组) 的数量
            long cnt = 0;
            // res: 至少需要选择的士兵数量
            long res = 0;
            // 遍历每个职业的士兵数量
            for (int i = 0; i < b.size(); i++) {
                // 计算该职业可以组成的完整纯职业小组的数量
                long fullGroups = b.get(i) / 3;
                // 累加到总的完整纯职业小组数量
                cnt += fullGroups;
                // 为了尽可能组成小组，先尝试用每个职业的士兵组成不完整的组 (1人或2人)
                // 最多使用每个职业的 2 个士兵
                long used = Math.min(b.get(i), 2);
                // 更新该职业剩余的士兵数量
                b.set(i, b.get(i) - used);
                // 累加到总的士兵数量
                res += used;
            }
            // 如果可以组成的完整纯职业小组数量小于 k，则无法满足国王的要求
            if (cnt < k) {
                System.out.println(-1); // 输出 -1 表示无法满足
                continue; // 跳到下一个测试用例
            }
            // c1: 剩余的，每个职业中，除以3余1的士兵数量
            long c1 = 0;
            // c2: 剩余的，每个职业中，除以3余2的士兵数量
            long c2 = 0;
            // c3: 剩余的，每个职业中，可以组成完整纯职业小组的士兵数量
            long c3 = 0;
            // 遍历每个职业剩余的士兵数量
            for (long x : b) {
                // 计算可以组成的完整纯职业小组的数量
                c3 += x / 3;
                // 计算除以 3 的余数
                x %= 3;
                // 根据余数更新 c1 和 c2
                if (x == 1) {
                    c1++;
                } else if (x == 2) {
                    c2++;
                }
            }
            // 已经组成了一些小组，所以 k 需要减 1
            k--;
            // 已经选择了一些士兵，所以 res 需要加 1
            res++;
            // 尽可能使用 c3 中的士兵组成完整纯职业小组
            long v = Math.min(k, c3);
            k -= v;
            c3 -= v;
            res += v * 3;
            // 尽可能使用 c2 中的士兵组成纯职业小组
            v = Math.min(k, c2);
            k -= v;
            c2 -= v;
            res += v * 2;
            // 尽可能使用 c1 中的士兵组成纯职业小组
            v = Math.min(k, c1);
            k -= v;
            c1 -= v;
            res += v;
            // 输出至少需要选择的士兵数量
            System.out.println(res);
        }
        // 关闭 Scanner
        scanner.close();
    }
}

